﻿using System.Collections.Generic;
using DeepEarth.Core;
using System;
using System.Windows;
using System.Linq;
using DeepEarth.Core.Data;
using DeepEarth.Core.Utilities;
using DeepEarth.Map.Core.Clustering;
namespace DeepEarth.Map.Core.Filters
{
    public class Clusterer
    {

        private double threshold = 20.0;
        public double Threshold
        {
            get
            {
                return threshold;
            }
            set
            {
                threshold = value;
            }
        }


        // Pixels per drgree, ignore aspect ratio
        private double pixelsPerDegree = -1;
        public double PixelsPerDegree
        {
            get
            {
                return pixelsPerDegree;
            }
            set
            {
                pixelsPerDegree = value;
            }
        }

        private double GetScreenDistance(Location loc1, Location loc2)
        {
            if (pixelsPerDegree <= 0)
            {
                throw new Exception("PixelsPerDegree has not been set. Screen Distance calculation impossible");
            }

            double angularDist = Location.GetAngularDistance(loc1, loc2);

            return angularDist * PixelsPerDegree;
        }

        // Attempt to split an existing cluster - this will attempt to retain the existing cluster as one of the new clusters.
        private List<ClusterViewModel> GreedilySplitExisting(ClusterViewModel existingCluster)
        {
            List<ClusterViewModel> clusters = new List<ClusterViewModel>();

            ClusterViewModel current = existingCluster;
            clusters.Add(current);

            if (!existingCluster.IsCluster)
            {
                return clusters;
            }

            List<ClusterViewModel> viewModels = existingCluster.GetClusteredItems();
            current.ClearCluster();

            while (viewModels.Count > 0)
            {
                foreach (ClusterViewModel vm in viewModels)
                {
                    if (GetScreenDistance(current.Position, vm.Position) <= Threshold)
                    {
                        current.AddToCluster(vm);
                    }
                }

                foreach (var child in current.GetClusteredItems())
                {
                    viewModels.Remove(child);
                }

                if (viewModels.Count > 0)
                {
                    current = viewModels[0];
                    clusters.Add(current);
                    viewModels.Remove(current);
                }
            }
            
            return clusters;
        }

        private List<ClusterViewModel> CoalesceClusters(List<ClusterViewModel> potentialClusters)
        {
            int outerCoalesceIndex = 0;
            int innerCoalesceIndex = 0;
            ClusterViewModel current;
            // compare each cluster, with every other cluster in the list.
            // at the end of this while loop, clusters that are close together will have been merged
            while (outerCoalesceIndex < potentialClusters.Count - 1)
            {
                current = potentialClusters[outerCoalesceIndex];
                innerCoalesceIndex = outerCoalesceIndex + 1;
                while (innerCoalesceIndex < potentialClusters.Count)
                {
                    ClusterViewModel candidate = potentialClusters[innerCoalesceIndex];

                    if (GetScreenDistance(current.Position, candidate.Position) <= Threshold)
                    {
                        // TODO: find out why this fails sometimes
                        try
                        {
                            current.AddToCluster(candidate);
                        }
                        catch
                        {
                        }
                        foreach (ClusterViewModel child in candidate.GetClusteredItems())
                        {
                            // TODO: find out why this fails sometimes
                            try
                            {
                                current.AddToCluster(child);
                            }
                            catch
                            {
                            }
                        }
                        candidate.ClearCluster();
                        potentialClusters.Remove(candidate);
                    }
                    else
                    {
                        innerCoalesceIndex++;
                    }
                }
                outerCoalesceIndex++;
            }

            return potentialClusters;
        }

        // visibleViewModels are those view models which shold be in the frame, clustered or otherwise. ExistingVisible are those view models which are actually visible on screen. Elements that are part of a
        // cluster but are not the representative icon of the cluster are not in existingVisible.
        public Dictionary<ClusterViewModel, ClusterViewModel> SimpleStreamCluster(Dictionary<ClusterViewModel, ClusterViewModel> visibleViewModels, Dictionary<ClusterViewModel, ClusterViewModel> existingVisible)
        {
            Dictionary<ClusterViewModel, ClusterViewModel> clusters = new Dictionary<ClusterViewModel, ClusterViewModel>();

            // Nothing to do, break early
            if (visibleViewModels == null || !visibleViewModels.Any())
            {
                // return empty list
                return clusters;
            }

            List<ClusterViewModel> potentialClusters = existingVisible.Keys.ToList();            

            // For the exising clusters, recluster them in isolation. - This will occur if there has been a zoomin.
            var existingClusters = potentialClusters.Where(c => c.IsCluster).ToList();

            List<ClusterViewModel> splitClisters = new List<ClusterViewModel>();

            foreach (var cluster in existingClusters)
            {
                List<ClusterViewModel> splits = GreedilySplitExisting(cluster);

                // if the cluster was split, remove it from the potentials and add the parts that were split into the potentials

                if (splits.Count > 1)
                {
                    potentialClusters.Remove(cluster);

                    foreach (var vm in splits)
                    {
                        potentialClusters.Add(vm);
                    }
                }
            }

            //we'd like to reuse the existing clusters so sort them first - this is the first step in preparation for coalescing
            //as we'd like to reuse exising clusters.
            potentialClusters = potentialClusters.OrderByDescending(c => c.GetClusterSize()).ToList();

            // Get a list of the new view models (All the view models that aren't already visible)
            // first get a list of all visible
            // Using a dictionary in lieu of a hashtable. We don't care about the value, only the key
            Dictionary<ClusterViewModel, byte> allExistingFlat = new Dictionary<ClusterViewModel, byte>();

            foreach (var cvm in potentialClusters)
            {
                // potentialClusters may be modified elsewhere
                if (allExistingFlat.ContainsKey(cvm))
                {
                    continue;
                }
                allExistingFlat.Add(cvm, 0);

                foreach (var child in cvm.GetClusteredItems())
                {
                    if (!allExistingFlat.ContainsKey(child))
                    {
                        allExistingFlat.Add(child, 0);
                    }
                }
            }

            // add the items that are newly in the frame to the potential clusters
            foreach (var kvp in visibleViewModels)
            {                
                if (!allExistingFlat.ContainsKey(kvp.Key))
                {
                    // If visibility has been turned off then on, some of the view models will already be clusters. We're working on the assumption
                    // that each is not a cluster so clear them out. (If visiblity has been turned off, the map manipulated, then turned on, we can't make use
                    // of these now visible clusters anyway)
                    kvp.Key.ClearCluster();

                    potentialClusters.Add(kvp.Key);
                }
            }

            potentialClusters = CoalesceClusters(potentialClusters);

            return potentialClusters.ToDictionary(c => c);
        }


        #region Alt Strategies
        //        enum MapAction {ZoomIn, ZoomOut, Pan};

        //private IEnumerable<GeoItemViewModel> StreamCluster(IEnumerable<GeoItemViewModel> visibleViewModels, List<GeoItemViewModel> existingViewModels, MapAction action)
        //{
        //    List<GeoItemViewModel> clusters = new List<GeoItemViewModel>();

        //    if (visibleViewModels == null || !visibleViewModels.Any())
        //    {
        //        // return empty list
        //        return clusters;
        //    }
        //    List<MatryoshkaViewModel> potentialClusters = new List<MatryoshkaViewModel>();

        //    // if zoomOut or pan, we can't just work with the list of existing viewmodels.             
        //    switch (action)
        //    {
        //        case MapAction.Pan :
        //            {
        //                // some viewModels have come into view - first remove all the existing view models that have been hidden

        //                int index = 0;
        //                while (index < existingViewModels.Count)
        //                {
        //                    GeoItemViewModel vm = existingViewModels[index];

        //                    if (vm is MatryoshkaViewModel)
        //                    {
        //                        MatryoshkaViewModel mvm = vm as MatryoshkaViewModel;

        //                        int i = 0;
        //                        while (i < mvm.Children.Count)
        //                        {
        //                            GeoItemViewModel child = mvm.Children[i];

        //                            if (visibleViewModels.Contains(child))
        //                            {
        //                                i++;
        //                            }
        //                            else
        //                            {
        //                                mvm.Children.Remove(child);
        //                            }
        //                        }

        //                        if (mvm.Children.Count == 0)
        //                        {
        //                            existingViewModels.Remove(mvm);
        //                        }
        //                        else
        //                        {
        //                            index++;
        //                        }
        //                    }
        //                    else
        //                    {
        //                        if (!visibleViewModels.Contains(vm))
        //                        {
        //                            existingViewModels.Remove(vm);
        //                        }
        //                        else
        //                        {
        //                            index++;
        //                        }
        //                    }

        //                }
        //                // ExistingViewModels is not consitant with what is visible. Do the same as ZoomOut
        //                goto case MapAction.ZoomOut;
        //            }
        //        case MapAction.ZoomOut:
        //            {

        //                // First, to make things easier, make everything a matryoshka view model
        //                List<MatryoshkaViewModel> existingClusters = new List<MatryoshkaViewModel>();
        //                foreach (GeoItemViewModel vm in existingViewModels)
        //                {
        //                    if (vm is MatryoshkaViewModel)
        //                    {
        //                        existingClusters.Add(vm as MatryoshkaViewModel);
        //                    }
        //                    else
        //                    {
        //                        MatryoshkaViewModel mvm = new MatryoshkaViewModel();
        //                        mvm.Position = vm.Position;
        //                        mvm.Children.Add(vm);
        //                        existingClusters.Add(mvm);
        //                    }                        
        //                }

        //                // Zooming out - coalesce exiting clusters if necessary
        //                // Pan actions also execute this code. We don't coalesce on a pan
        //                if (MapAction.ZoomOut == action)
        //                {
        //                    int outerCoalesceIndex = 0;
        //                    int innerCoalesceIndex = 0;
        //                    MatryoshkaViewModel current;
        //                    // compare each cluster, with every other cluster in the list.
        //                    // at the end of this while loop, clusters that are close together will have been merged
        //                    while (outerCoalesceIndex < existingClusters.Count -1 )
        //                    {
        //                        current = existingClusters[outerCoalesceIndex];
        //                        innerCoalesceIndex = outerCoalesceIndex + 1;
        //                        while (innerCoalesceIndex < existingClusters.Count)
        //                        {
        //                            MatryoshkaViewModel candidate = existingClusters[innerCoalesceIndex];
        //                            if (GetScreenDistance(current.Position, candidate.Position) <= threshold)
        //                            {
        //                                foreach (GeoItemViewModel child in candidate.Children)
        //                                {
        //                                    current.Children.Add(child);
        //                                }
        //                                existingClusters.Remove(candidate);
        //                            }
        //                            else
        //                            {
        //                                innerCoalesceIndex++;
        //                            }
        //                        }
        //                        outerCoalesceIndex++;
        //                    }
        //                }

        //                // Get a list of the new view models (All the view models that aren't already visible)
        //                IEnumerable<GeoItemViewModel> allNonClustered = existingViewModels.Where(vm => !(vm is MatryoshkaViewModel));
        //                IEnumerable<GeoItemViewModel> allClustered = existingViewModels.OfType<MatryoshkaViewModel>().SelectMany(mvm => mvm.Flatten());
        //                IEnumerable<GeoItemViewModel> allExistingFlat = allNonClustered.Concat(allClustered);

        //                // newlyInFrame is the collection of newly visible view models
        //                List<GeoItemViewModel> newlyInFrame = new List<GeoItemViewModel>();

        //                foreach (GeoItemViewModel vm in visibleViewModels)
        //                {
        //                    if (!allExistingFlat.Contains(vm))
        //                    {
        //                        newlyInFrame.Add(vm);
        //                    }
        //                }

        //                // make use of the exising clusters - or create new ones.
        //                // Add each new viewModel to an exising cluster where appropriate. If the new viewmodel
        //                // does not belong in an existing cluster, make a new one.
        //                foreach (GeoItemViewModel newlyAdded in newlyInFrame)
        //                {
        //                    bool clusteredInExisting = false;

        //                    foreach (MatryoshkaViewModel existingCluster in existingClusters)
        //                    {
        //                        if (GetScreenDistance(existingCluster.Position, newlyAdded.Position) <= threshold)
        //                        {
        //                            existingCluster.Children.Add(newlyAdded);
        //                            clusteredInExisting = true;
        //                            continue;
        //                        }
        //                    }

        //                    if (!clusteredInExisting)
        //                    {
        //                        MatryoshkaViewModel mvm = new MatryoshkaViewModel();
        //                        mvm.Position = newlyAdded.Position;
        //                        mvm.Children.Add(newlyAdded);
        //                        existingClusters.Add(mvm);
        //                    }
        //                }

        //                potentialClusters = existingClusters;

        //                // this filter is supposed to return a list of clusters and single view models. Compile that collection now.
        //                clusters = potentialClusters.Where(p => p.Children.Count > 1).Select(p => p as GeoItemViewModel).ToList();
        //                clusters = clusters.Concat(potentialClusters.Where(p => p.Children.Count == 1).Select(p => p.Children[0])).ToList();

        //                break;
        //            }

        //        case MapAction.ZoomIn :
        //            // if we're zooming in, recluster each exising cluster in isolation
        //            // Just use the exising QTClusting algorithm.
        //            {
        //                // First get all the view models that aren't clusters. (zooming in, so they won't get clustered)
        //                clusters = existingViewModels.Where(e => !(e is MatryoshkaViewModel)).ToList();

        //                // For the exising clusters, recluster them in isolation.
        //                var existingClusters = existingViewModels.OfType<MatryoshkaViewModel>();

        //                //var reclustered = existingClusters.SelectMany(e => QTClustering(e.Children));

        //                var reclustered = existingClusters.SelectMany(e => GreedyClustering(e.Children));
        //                clusters = clusters.Concat(reclustered).ToList();
        //            }

        //            break;
        //    }


        //    return clusters;


        //}

        //private IEnumerable<GeoItemViewModel> QTClustering(IEnumerable<GeoItemViewModel> viewModels)
        //{
        //    List<GeoItemViewModel> clusters = new List<GeoItemViewModel>();

        //    if (viewModels == null || !viewModels.Any())
        //    {
        //        // return empty list
        //        return clusters;
        //    }


        //    // 1. Create a list of potential clusters
        //    List<MatryoshkaViewModel> potentialClusters = new List<MatryoshkaViewModel>();
        //    foreach (GeoItemViewModel viewModel in viewModels)
        //    {
        //        GeoItemViewModel representative = viewModel;

        //        MatryoshkaViewModel mvm = new MatryoshkaViewModel();
        //        mvm.Position = representative.Position;
        //        mvm.Children.Add(representative);

        //        foreach (GeoItemViewModel vm in viewModels.Where(element => element != representative))
        //        {
        //            if (GetScreenDistance(representative.Position, vm.Position) <= Threshold)
        //            {
        //                mvm.Children.Add(vm);
        //            }
        //        }

        //        potentialClusters.Add(mvm);
        //    }

        //    // 2. Extract the actual clusters
        //    while (true)
        //    {

        //        //3 . Find the largest cluster
        //        MatryoshkaViewModel largest = potentialClusters[0];
        //        int largestCount = largest.Descendents;

        //        potentialClusters.Iter(c =>
        //            {
        //                int currentCount = c.Descendents;
        //                if (currentCount > largestCount)
        //                {
        //                    largest = c;
        //                    largestCount = currentCount;
        //                }
        //            }
        //        );


        //        // 4. Remove duplicates. If an element appears in the largest cluster, it should not appear elsewhere
        //        if (largest.Children.Count > 1)
        //        {
        //            clusters.Add(largest);

        //            potentialClusters.Remove(largest);

        //            List<MatryoshkaViewModel> empties = new List<MatryoshkaViewModel>();
        //            // if a viewmodel in the largest cluster appears in other clusters, remove it.

        //            foreach (MatryoshkaViewModel other in potentialClusters)
        //            {
        //                foreach (GeoItemViewModel child in largest.Children)
        //                {
        //                    if (other.Children.Contains(child))
        //                    {
        //                        other.Children.Remove(child);

        //                        if (other.Children.Count == 0)
        //                        {
        //                            empties.Add(other);
        //                        }
        //                    }
        //                }
        //            }

        //            // remove the empty clusters
        //            empties.Iter(e => potentialClusters.Remove(e));

        //            if (potentialClusters.Count == 0)
        //            {
        //                break;
        //            }
        //        }
        //        else
        //        {
        //            // if the largest has only one, then so do the rest. Flatten and return
        //            clusters = clusters.Concat(potentialClusters.Where(p => p.Children.Count > 0).Select(p => p.Children[0])).ToList();
        //            break;
        //        }
        //    }

        //    return clusters;

        //}

        //private List<GeoItemViewModel> GreedyClustering(List<GeoItemViewModel> viewModels)
        //{
        //    List<GeoItemViewModel> clusters = new List<GeoItemViewModel>();

        //    if (viewModels.Count == 0)
        //    {
        //        return clusters;
        //    }

        //    int index = 0;
        //    while (index < viewModels.Count())
        //    {
        //        GeoItemViewModel current = viewModels[index];

        //        MatryoshkaViewModel mvm = new MatryoshkaViewModel();
        //        mvm.Position = current.Position;
        //        mvm.Children.Add(current);

        //        foreach (GeoItemViewModel vm in viewModels.Where(v => v != current))
        //        {
        //            if (GetScreenDistance(current.Position, vm.Position) <= Threshold)
        //            {

        //                mvm.Children.Add(vm);
        //            }
        //        }

        //        if (mvm.Children.Count > 1)
        //        {
        //            clusters.Add(mvm);

        //            foreach (GeoItemViewModel child in mvm.Children)
        //            {
        //                viewModels.Remove(child);
        //            }
        //        }
        //        else
        //        {
        //            index++;
        //        }

        //    }

        //    foreach (GeoItemViewModel vm in viewModels)
        //    {
        //        clusters.Add(vm);
        //    }

        //    return clusters;
        //}
        #endregion
    }
}
